4.7 KB · ⇊ 3 parts · ⤓ Micron 4.7 KB · ⤓ HTML 39.0 KB

top

In quantum computing, the Brassard–Høyer–Tapp algorithm or BHT algorithm is a quantum algorithm that solves the collision problem. In this problem, one is given n and an r-to-1 function f : { 1 , … … , n } → → { 1 , … … , n } {\displaystyle f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}} and needs to find two inputs that f maps to the same output. The BHT algorithm only makes O ( n 1 / 3 ) {\displaystyle O(n^{1/3})} queries to f, which matches the lower bound of Ω Ω ( n 1 / 3 ) {\displaystyle \Omega (n^{1/3})} in the black box model.cite-ref-1[1]cite-ref-2[2]

The algorithm was discovered by Gilles Brassard, Peter Høyer, and Alain Tapp in 1997.cite-ref-0-3-0[3] It uses Grover's algorithm, which was discovered the year before.

• Algorithm

• See also

• References

Intuitively, the algorithm combines the square root speedup from the birthday paradox using (classical) randomness with the square root speedup from Grover's (quantum) algorithm.

First, n1/3 inputs to f are selected at random and f is queried at all of them. If there is a collision among these inputs, then we return the colliding pair of inputs. Otherwise, all these inputs map to distinct values by f. Then Grover's algorithm is used to find a new input to f that collides. Since there are n inputs to f and n1/3 of these could form a collision with the already queried values, Grover's algorithm can find a collision with O ( n n 1 / 3 ) = O ( n 1 / 3 ) {\displaystyle O\left({\sqrt {\frac {n}{n^{1/3}}}}\right)=O(n^{1/3})} extra queries to f.cite-ref-0-3-1[3]

• Element distinctness problem

• Grover's algorithm

cite-note-11. ↑ citerefambainis2005Ambainis, A. (2005). "Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range" (PDF). Theory of Computing. 1 (1): 37–46. doi:10.4086/toc.2005.v001a003.

cite-note-22. ↑ citerefkutin2005Kutin, S. (2005). "Quantum Lower Bound for the Collision Problem with Small Range". Theory of Computing. 1 (1): 29–36. doi:10.4086/toc.2005.v001a002.

cite-note-0-33. ↑ citerefbrassardh-yertapp1998Brassard, Gilles; Høyer, Peter; Tapp, Alain (1998), "Quantum Algorithm for the Collision Problem", in Lucchesi, Claudio L.; Moura, Arnaldo V. (eds.), LATIN '98: Theoretical Informatics, Third Latin American Symposium, Campinas, Brazil, April, 20-24, 1998, Proceedings, Lecture Notes in Computer Science, vol. 1380, Springer, pp. 163–169, arXiv:quant-ph/9705002, doi:10.1007/BFb0054319, S2CID 3116149